// https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
package leet19removenthnodefromend

// 思路：
// 1. 定义一个虚拟头节点dummy，指向head
// 2. 定义两个指针first和second，初始值都为dummy
// 3. first指针先向前移动n+1步，second指针不动
// 4. 然后两个指针一起向前移动，直到first指针到达链表的末尾
// 5. 此时second指针指向的节点就是要删除的节点的前一个节点
// 6. 将second指针的next指针指向要删除的节点的下一个节点
// 7. 返回dummy的next指针，即为新的头节点
// 8. 注意：如果链表只有一个节点，删除后返回nil
// 9. 时间复杂度O(n)，空间复杂度O(1)
// 限制条件：

func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	// 创建一个虚拟头节点，方便处理删除头节点的情况
	dummy := &ListNode{Next: head}
	first := dummy
	second := dummy
	// first指针先向前移动n+1步，second指针不动
	for i := 0; i < n+1; i++ {
		first = first.Next
	}
	// 然后两个指针一起向前移动，直到first指针到达链表的末尾
	for first != nil {
		first = first.Next
		second = second.Next
	}
	// 此时second指针指向的节点就是要删除的节点的前一个节点
	second.Next = second.Next.Next
	return dummy.Next
}

// Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}
